import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-02-24
 * Time: 16:26
 */
public class test1 {
    /**
     * LeetCode 692  前k个高频单词
     */
    public List<String> topKFrequent(String[] words, int k) {
        // 1.统计每一个单词出现的频次
        Map<String,Integer> hash = new HashMap<>();
        for(String s : words){
            hash.put(s,hash.getOrDefault(s,0)+1);
        }
        // 2.创建一个大小为k的堆
        PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<Pair<String, Integer>>(
                (a,b) ->{
                    if(a.getValue().equals(b.getValue())){
                        return b.getKey().compareTo(a.getKey());
                    }
                    return a.getValue()-b.getValue();
                }
        );

        // 3.TopK
        for(Map.Entry<String,Integer> e: hash.entrySet()){
            heap.offer(new Pair<>(e.getKey(),e.getValue()));
            if(heap.size()>k){
                heap.poll();
            }
        }

        // 4.提取结果
        List<String> ret = new ArrayList<>();
        while(!heap.isEmpty()){
            ret.add(heap.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}
